class Node:
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class TreeDemo:
    def __init__(self, root=None):
        self.root = root

    def add(self, elem):
        node = Node(elem)
        if self.root is None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            while queue:
                root_node = queue.pop(0)
                if root_node.lchild is None:
                    root_node.lchild = node
                    return
                if root_node.rchild is None:
                    root_node.rchild = node
                    return
                queue.append(root_node.lchild)
                queue.append(root_node.rchild)

    def preorder(self, root):
        if root is None:
            return
        print(root.elem, end=' ')
        self.preorder(root.lchild)
        self.preorder(root.rchild)

    def preorder_nonrecursive(self, root):
        if root is None:
            return
        self.root = root
        queue = []
        while self.root or queue:
            while self.root:
                print(self.root.elem, end=' ')
                queue.append(self.root)
                self.root = self.root.lchild
            node = queue.pop()
            self.root = node.rchild

    def inorder(self, root):
        if root is None:
            return
        self.inorder(root.lchild)
        print(root.elem, end=' ')
        self.inorder(root.rchild)

    def inorder_nonrecursive(self, root):
        if root is None:
            return
        self.root = root
        queue = []
        while self.root or queue:
            while self.root:
                queue.append(self.root)
                self.root = self.root.lchild
            node = queue.pop()
            print(node.elem, end=" ")
            self.root = node.rchild

    def postorder(self, root):
        if root is None:
            return
        self.postorder(root.lchild)
        self.postorder(root.rchild)
        print(root.elem, end=' ')

    def postorder_nonrecursive(self, root):
        if root is None:
            return
        self.root = root
        queue1 = []
        queue2 = []
        queue1.append(self.root)
        while queue1:
            node = queue1.pop()
            if node.lchild:
                queue1.append(node.lchild)
            if node.rchild:
                queue1.append(node.rchild)
            queue2.append(node)
        while queue2:
            print(queue2.pop().elem, end=" ")

    def search_width(self, root):
        if root is None:
            return
        queue = []
        queue.append(root)
        while queue:
            root_node = queue.pop(0)
            print(root_node.elem, end=' ')
            if root_node.lchild:
                queue.append(root_node.lchild)
            if root_node.rchild:
                queue.append(root_node.rchild)

    def _test_preorder(self):
        """
        sd = TreeDemo()
        sd._test_preorder()
        """
        self.add(11)
        self.add(22)
        self.add(3)
        self.add(77)
        self.add(66)
        self.add(88)  # 11 22 3 77 66 88
        #      11
        #   22    3
        # 77 66 88
        self.preorder(self.root)  # 11 22 77 66 3 88

    def _test_inorder(self):
        """
        sd = TreeDemo()
        sd._test_inorder()
        """
        self.add(11)
        self.add(22)
        self.add(3)
        self.add(77)
        self.add(66)
        self.add(88)  # 11 22 3 77 66 88
        #      11
        #   22    3
        # 77 66 88
        self.inorder(self.root)  # 77 22 66 11 88 3

    def _test_postorder(self):
        """
        sd = TreeDemo()
        sd._test_postorder()
        """
        self.add(11)
        self.add(22)
        self.add(3)
        self.add(77)
        self.add(66)
        self.add(88)  # 11 22 3 77 66 88
        #      11
        #   22    3
        # 77 66 88
        self.postorder(self.root)  # 77 66 22 88 3 11

    def _test_preorder_nonrecursive(self):
        """
        sd = TreeDemo()
        sd._test_preorder_nonrecursive()
        """
        self.add(11)
        self.add(22)
        self.add(3)
        self.add(77)
        self.add(66)
        self.add(88)  # 11 22 3 77 66 88
        #      11
        #   22    3
        # 77 66 88
        self.preorder_nonrecursive(self.root)  # 11 22 77 66 3 88

    def _test_inorder_nonrecursive(self):
        """
        sd = TreeDemo()
        sd._test_inorder_nonrecursive()
        """
        self.add(11)
        self.add(22)
        self.add(3)
        self.add(77)
        self.add(66)
        self.add(88)  # 11 22 3 77 66 88
        #      11
        #   22    3
        # 77 66 88
        self.inorder_nonrecursive(self.root)  # 77 22 66 11 88 3

    def _test_postorder_nonrecursive(self):
        """
        sd = TreeDemo()
        sd._test_postorder_nonrecursive()
        """
        self.add(11)
        self.add(22)
        self.add(3)
        self.add(77)
        self.add(66)
        self.add(88)  # 11 22 3 77 66 88
        #      11
        #   22    3
        # 77 66 88
        self.postorder_nonrecursive(self.root)  # 77 66 22 88 3 11

    def _test_search_width(self):
        """
        sd = TreeDemo()
        sd._test_search_width()
        """
        self.add(11)
        self.add(22)
        self.add(3)
        self.add(77)
        self.add(66)
        self.add(88)  # 11 22 3 77 66 88
        #      11
        #   22    3
        # 77 66 88
        self.search_width(self.root)  # 11 22 3 77 66 88


class SearchDemo:
    def search_binary(self, alist, item):
        n = len(alist)
        if n == 0:
            return False
        else:
            mid = n // 2
            if alist[mid] == item:
                return True
            elif alist[mid] < item:
                return self.search_binary(alist[mid + 1:], item)
            else:
                return self.search_binary(alist[:mid], item)

    def _test_search_binary(self):
        """
        sd = SearchDemo()
        sd._test_search_binary()
        """
        li = [11, 22, 3, 77, 66, 88]
        sd = SearchDemo()
        print(sd.search_binary(li, 77))
        print(sd.search_binary(li, 55))


if __name__ == '__main__':
    sd = TreeDemo()
    sd._test_search_width()
